package cn.javadog.algorithm.e1_100;

/**
 * 最长公共前缀
 * https://leetcode-cn.com/problems/longest-common-prefix/
 * @author Sprite
 */
public class Algorithm14 {
	public static void main(String[] args) {
		System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"}));
		System.out.println(longestCommonPrefix(new String[]{"dog","racecar","car"}));
	}


	public static String longestCommonPrefix(String[] strs) {
		if (strs.length == 0) return "";
		for (String str : strs) {
			if (str == null) return "";
		}

		String base = strs[0];
		for (int i = 0; i < base.length(); i++) {
			char c = base.charAt(i);
			for (int j = 0; j < strs.length; j++) {
				if (strs[j].length() == i || strs[j].charAt(i) != c) {
					return i==0 ? "" : base.substring(0,i);
				}
			}
		}

		return base;
	}
}
